#include <math.h> // for power

#include "Optimizer.h"
#include "SpaEnumTranslator.h"


Optimizer::Optimizer(const ClauseSet& clauses, SynonymTable *synTable, PKB *pkb)
{
	mClauses = clauses;
	mSynTable = synTable;
	mPkb = pkb;
	mLeastComplexityClause = -1; // no least complexity clause found yet
	
	initialize(pkb);
}


Optimizer::~Optimizer(void)
{
}

void Optimizer::initialize(PKB *pkb) {
	initializeRelTimeComplexities(pkb);
	initializePatTimeComplexities(pkb);
	initializeConTimeComplexities(pkb);

	initializeRelResultComplexities(pkb);
	initializePatResultComplexities(pkb);
	initializeConResultComplexities(pkb);
}


void Optimizer::initializeRelTimeComplexities(PKB *pkb) {
	// Types:
	// AFFECTSBIP, AFFECTSBIP_STAR
	// NEXTBIP, NEXTBIP_STAR
	// CONTAINS, CONTAINS_STAR
	// SIBLING,
	// AFFECTS, AFFECTS_STAR,
	// NEXT, NEXT_STAR,
	// CALL, CALL_STAR,
	// FOLLOWS, FOLLOWS_STAR
	// MODIFIES_LINE, MODIFIES_PROC,
	// USES_LINE, USES_PROC,
	// PARENT, PARENT_STAR,
	
	unsigned int numLinesInProg = numLinesInProgram(pkb);
	unsigned int numAssignsInProg = numAssignsInProgram(pkb);
	unsigned int numCallsInProg = numCallsInProgram(pkb);
	// O(Calls) = 1 (call table lookup)
	relTimeComplexities.insert( std::make_pair(CALLS, 1) );
	// O(Calls*) = 1 (call* table lookup)
	relTimeComplexities.insert( std::make_pair(CALLS_STAR, 1) );
	// O(LineModifies) = 1 (LineModifies table lookup)
	relTimeComplexities.insert( std::make_pair(MODIFIES_LINE, 1) );
	// O(LineUses) = 1 (LineUses table lookup)
	relTimeComplexities.insert( std::make_pair(USES_LINE, 1) );
	// O(ProcModifies) = 1 (ProcModifies table lookup)
	relTimeComplexities.insert( std::make_pair(MODIFIES_PROC, 1) );
	// O(ProcUses) = 1 (ProcUses table lookup)
	relTimeComplexities.insert( std::make_pair(USES_PROC, 1) );
	// O(Parent) = 1 (Parent table lookup)
	relTimeComplexities.insert( std::make_pair(PARENT, 1) );
	// O(Parent*) = 1 (Parent* table lookup)
	relTimeComplexities.insert( std::make_pair(PARENT_STAR, 1) );
	// O(Follows) = 1 (Follows table lookup)
	relTimeComplexities.insert( std::make_pair(FOLLOWS, 1) );
	// O(Follows*) = 1 (Follows* table lookup)
	relTimeComplexities.insert( std::make_pair(FOLLOWS_STAR, 1) );
	// O(Next) = 1 (Next table (CFG) lookup)
	relTimeComplexities.insert( std::make_pair(NEXT, 1) );
	// O(Next*) = 5 (Optimized to O(1))
	relTimeComplexities.insert( std::make_pair(NEXT_STAR, 5) );
	// O(Affects) = 10 (Optimized to O(1), but not as fast as Next*)
	relTimeComplexities.insert( std::make_pair(AFFECTS, 10) );
	// O(Affects*) = number of lines in the program (traverse the Affects graph)
	relTimeComplexities.insert( std::make_pair(AFFECTS_STAR, (int)pow(numAssignsInProg, 1.5)) );
	// O(NextBIP) = 1 (NextBIP table (CFGBIP) lookup)
	relTimeComplexities.insert( std::make_pair(NEXTBIP, 1) );
	// O(NextBIP*) = Optimized algorithm that runs in O(c) time, c = no. of call stmts in program
	relTimeComplexities.insert( std::make_pair(NEXTBIP_STAR, numCallsInProg) );
	// O(AffectsBIP) = Optimized algorithm that runs in O(c) time, c = no. of call stmts in program
	relTimeComplexities.insert( std::make_pair(AFFECTSBIP, numCallsInProg) );
	// O(AffectsBIP*) = Algorithm which uses affectsBIP to check all other assign stmts, and althought worse case is O(a^2 * c), it is unlikely
	relTimeComplexities.insert( std::make_pair(AFFECTSBIP_STAR, (int)(pow(numAssignsInProg, 1.5) * numCallsInProg)) );

	
	// TODO, CONTAINS NOT IMPLEMENTED
	relTimeComplexities.insert( std::make_pair(CONTAINS, 1) );
	// TODO, CONTAINS_STAR NOT IMPLEMENTED
	relTimeComplexities.insert( std::make_pair(CONTAINS_STAR, 1) );
	// TODO, SIBLING NOT IMPLEMENTED
	relTimeComplexities.insert( std::make_pair(SIBLING, 1) );
}

void Optimizer::initializePatTimeComplexities(PKB *pkb) {
	// Types:
	// PATTERN_ASSIGN
	// PATTERN_IF
	// PATTERN_WHILE

	// O(PATTERN_WHILE) = 3 (O(1), but have to traverse down from a while stmt node to check)
	patTimeComplexities.insert( std::make_pair(PATTERN_WHILE, 3) );
	// O(PATTERN_IF) = 5 (O(1), but have to traverse down from a if stmt node to check. Also, more children than while stmt nodes)
	patTimeComplexities.insert( std::make_pair(PATTERN_IF, 5) );
	// O(PATTERN_ASSIGN) = 7 (O(1), but on the average case would still have to traverse down a little bit of the subtree
	// in which the root is a given assignment stmt node to find if the pattern is satisfied or not)
	patTimeComplexities.insert( std::make_pair(PATTERN_ASSIGN, 7) );
}

void Optimizer::initializeConTimeComplexities(PKB *pkb) {
	// Types:
	// WITH_INTEGER
	// WITH_STRING

	// WITH_INTEGER
	// can have s1.stmt# = s2.stmt# but this is removed by queryPreprocessor
	// so we only have stuff like c1.value = c2.value and s1.stmt# = c1.value.
	// Take the maximum
	/*int numConstantsInProg = numConstantsInProgram(pkb);
	int numLinesInProg= numLinesInProgram(pkb);
	int complexityForWithInteger = (numConstantsInProg > numLinesInProg) ? numConstantsInProg : numLinesInProg;*/
	//conTimeComplexities.insert( std::make_pair(WITH_INTEGER, complexityForWithInteger) );

	// WITH_INTEGER 
	// Just compare left value with right value
	conTimeComplexities.insert( std::make_pair(WITH_INTEGER, 1) );

	// WITH_STRING
	// can have p.procName = c.procName or
	// p.procName = v.varName
	// Take the largest of these (procedures or variables)
	/*int numProcsInProg = numProcsInProgram(pkb);
	int numVarsInProg = numVarsInProgram(pkb);
	int complexityForWithString = (numProcsInProg > numVarsInProg) ? numProcsInProg : numVarsInProg;
	conTimeComplexities.insert( std::make_pair(WITH_STRING, complexityForWithString) );*/

	// WITH_STRING
	// Just compare left value with right value
	conTimeComplexities.insert( std::make_pair(WITH_STRING, 1) );
}

void Optimizer::initializeRelResultComplexities(PKB *pkb) {
	// Types:
	// AFFECTSBIP, AFFECTSBIP_STAR
	// NEXTBIP, NEXTBIP_STAR
	// CONTAINS, CONTAINS_STAR
	// SIBLING,
	// AFFECTS, AFFECTS_STAR,
	// NEXT, NEXT_STAR,
	// CALL, CALL_STAR,
	// FOLLOWS, FOLLOWS_STAR
	// MODIFIES_LINE, MODIFIES_PROC,
	// USES_LINE, USES_PROC,
	// PARENT, PARENT_STAR,

	int numLinesInProg = numLinesInProgram(pkb);
	int numProcsInProg = numProcsInProgram(pkb);
	int numAssignsInProg = numAssignsInProgram(pkb);
	int largestNumberOfChildren = largestNumberOfChildrenInOneParent(pkb);
	int maxLinesInOneProc = maxLinesInOneProcedure(pkb);
	// O(Calls) = number of procs - 1 (1 proc can at most call all other procs, but not itself)
	relResultComplexities.insert( std::make_pair(CALLS, numProcsInProg - 1) );
	// O(Calls*) = (number of procs - 1) * 3/2 (same as Calls, but * 3/2 to say that 
	// calls* has a higher chance of having more results)
	relResultComplexities.insert( std::make_pair(CALLS_STAR, (numProcsInProg - 1)*3/2) );
	// O(LineModifies) = (number of lines) / 4 
	// (arbitrary /4 to say that it is unlikely that all assign stmts modify a given variable)
	relResultComplexities.insert( std::make_pair(MODIFIES_LINE, numLinesInProg/4) );
	// O(LineUses) = (number of Lines) / 2 
	// (arbitrary /2 to say that it is unlikely that all assign stmts use a given variable, but more likely than lineModifies)
	relResultComplexities.insert( std::make_pair(USES_LINE, numLinesInProg/2) );
	// O(ProcModifies) = number of procedures
	relResultComplexities.insert( std::make_pair(MODIFIES_PROC, numProcsInProg) );
	// O(ProcUses) = number of procedures
	relResultComplexities.insert( std::make_pair(USES_PROC, numProcsInProg) );
	// O(Parent) = largest number of children in one parent
	relResultComplexities.insert( std::make_pair(PARENT, largestNumberOfChildren) );
	// O(Parent*) = largest number of children in one parent * 2 
	// (arbitrary 2 to say that on average the results will be twice)
	relResultComplexities.insert( std::make_pair(PARENT_STAR, largestNumberOfChildren*2) );
	// O(Follows) = 1 (a stmt can only follow/be followed by one other stmt at most
	relResultComplexities.insert( std::make_pair(FOLLOWS, 1) );
	// O(Follows*) = maximum number of lines in a procedure
	relResultComplexities.insert( std::make_pair(FOLLOWS_STAR, maxLinesInOneProc) );
	// O(Next) = 2 (arbitrary 2, because it is roughly O(1), but increases based on how many nested-if stmts there are)
	relResultComplexities.insert( std::make_pair(NEXT, 2) );
	// O(Next*) = maximum number of lines in a proc * 3/4 
	// (arbitrary 3/4 to say that on average it is not going to be all the lines that next* each other)
	relResultComplexities.insert( std::make_pair(NEXT_STAR, maxLinesInOneProc*3/4) );
	// O(Affects) = maximum number of lines in a proc / 3
	// (arbitrary 3 to say that it is not likely that one line affects/is affected by all other lines
	relResultComplexities.insert( std::make_pair(AFFECTS, maxLinesInOneProc/3) );
	// O(Affects*) = (maximum number of lines in a proc / 3) ^ 1.5
	// (arbitrary ^1.5 to say that the number of results from affects* is likely to be significantly more than affects)
	relResultComplexities.insert( std::make_pair(AFFECTS_STAR, (int)pow(maxLinesInOneProc/3, 1.5)) );
	// O(NextBIP) = 2 (same as Next)
	relResultComplexities.insert( std::make_pair(NEXTBIP, 2) );
	// O(NextBIP*) = number of lines in program * 3/4
	// (arbitrary 3/4 to say that on average it is not going to be all the lines that nextBIP* each other)
	relResultComplexities.insert( std::make_pair(NEXTBIP_STAR, numLinesInProg*3/4) );
	// O(AffectsBIP) = number of lines in program / 3
	// (arbitrary 3 to say that it is not likely that one line affects/is affected by all other lines
	relResultComplexities.insert( std::make_pair(AFFECTSBIP, numLinesInProg/3) );
	// O(AffectsBIP*) = (maximum number of lines in program / 3) ^ 1.5
	// (arbitrary ^1.5 to say that the number of results from affectsBIP* is likely to be significantly more than affectsBIP)
	relResultComplexities.insert( std::make_pair(AFFECTSBIP_STAR, (int)pow(numLinesInProg/3, 1.5)) );

	// TODO, CONTAINS NOT IMPLEMENTED
	relResultComplexities.insert( std::make_pair(CONTAINS, 1) );
	// TODO, CONTAINS_STAR NOT IMPLEMENTED
	relResultComplexities.insert( std::make_pair(CONTAINS_STAR, 1) );
	// TODO, SIBLING NOT IMPLEMENTED
	relResultComplexities.insert( std::make_pair(SIBLING, 1) );
}

void Optimizer::initializePatResultComplexities(PKB *pkb) {
	// Types:
	// PATTERN_ASSIGN
	// PATTERN_IF
	// PATTERN_WHILE
	
	int numWhiles = numWhilesInProgram(pkb);
	int numIfs = numIfsInProgram(pkb);
	int numAssigns = numAssignsInProgram(pkb);
	// O(PATTERN_WHILE) = number of while stmts/3
	// (arbitrary /3 to say that it is not likely that the pattern satisfies all assign stmts)
	patResultComplexities.insert( std::make_pair(PATTERN_WHILE, numWhiles/3) );
	// O(PATTERN_IF) = number of if stmts/3
	// (arbitrary /3 to say that it is not likely that the pattern satisfies all assign stmts)
	patResultComplexities.insert( std::make_pair(PATTERN_IF, numIfs/3) );
	// O(PATTERN_ASSIGN) = number of assign stmts/3
	// (arbitrary /3 to say that it is not likely that the pattern satisfies all assign stmts)
	patResultComplexities.insert( std::make_pair(PATTERN_ASSIGN, numAssigns/3) );
}

void Optimizer::initializeConResultComplexities(PKB *pkb) {
	// Types:
	// WITH_INTEGER
	// WITH_STRING

	// WITH_INTEGER
	// 1 result for 1 integer, because they have to be exactly equal!
	conResultComplexities.insert( std::make_pair(WITH_INTEGER, 1) );

	// WITH_STRING
	// can have p.procName = c.procName or
	// p.procName = v.varName
	// All are 1-1 mappings EXCEPT for c.procName.
	// So, use number of call stmts / 2 (arbitrary 2 to say that not likely that all call stmts will call a procedure)
	// If that number is 0, use 1.
	int numCalls = numCallsInProgram(pkb);
	int complexityForWithString = numCalls/2;
	if (complexityForWithString == 0) {
		complexityForWithString = 1;
	}
	conResultComplexities.insert( std::make_pair(WITH_STRING, complexityForWithString) );
}

unsigned int Optimizer::numLinesInProgram(PKB *pkb) {
	return pkb->getLines().size();
}

unsigned int Optimizer::numConstantsInProgram(PKB *pkb) {
	return pkb->getConstants().size();
}

unsigned int Optimizer::numProcsInProgram(PKB *pkb) {
	return pkb->getProcIndices().size();
}

unsigned int Optimizer::numVarsInProgram(PKB *pkb) {
	return pkb->getVarIndices().size();
}

unsigned int Optimizer::numAssignsInProgram(PKB *pkb) {
	return pkb->getLinesByEntity(Type::Entity::ASSIGNMENT_LINE_ENTITY).size();
}

unsigned int Optimizer::numWhilesInProgram(PKB *pkb) {
	return pkb->getLinesByEntity(Type::Entity::WHILE_LINE_ENTITY).size();
}

unsigned int Optimizer::numIfsInProgram(PKB *pkb) {
	return pkb->getLinesByEntity(Type::Entity::IF_LINE_ENTITY).size();
}

unsigned int Optimizer::numCallsInProgram(PKB *pkb) {
	return pkb->getLinesByEntity(Type::Entity::CALL_LINE_ENTITY).size();
}

unsigned int Optimizer::largestNumberOfChildrenInOneParent(PKB *pkb) {
	unsigned int largestNumberOfChildren = 0;
	Type::List::Line ifStmts = pkb->getLinesByEntity(Type::Entity::IF_LINE_ENTITY);
	Type::List::Line whileStmts = pkb->getLinesByEntity(Type::Entity::WHILE_LINE_ENTITY);
	for (unsigned int i = 0; i < ifStmts.size(); i++) {
		unsigned int numChildren = pkb->getChild(ifStmts.at(i)).size();
		if (numChildren > largestNumberOfChildren) {
			largestNumberOfChildren = numChildren;
		}
	}
	for (unsigned int i = 0; i < whileStmts.size(); i++) {
		unsigned int numChildren = pkb->getChild(whileStmts.at(i)).size();
		if (numChildren > largestNumberOfChildren) {
			largestNumberOfChildren = numChildren;
		}
	}
	return largestNumberOfChildren;
}

unsigned int Optimizer::maxLinesInOneProcedure(PKB *pkb) {
	unsigned int maxLines = 0;
	Type::List::Proc procs = pkb->getProcIndices();
	for (unsigned int i = 0; i < procs.size(); i++) {
		Type::Pair::StartEnd startEnd = pkb->getProcStartEnd(procs.at(i));
		int numLinesInProc = startEnd.second - startEnd.first + 1;
		if (numLinesInProc > (int)maxLines) {
			maxLines = numLinesInProc;
		}
	}
	return maxLines;
}

/// Splits the given clause set up into independent clause sets and returns them.
Optimizer::ClauseSets Optimizer::splitIndependentClauses(const ClauseSet& clauses) {
	ClauseSets independentClauseSets;
	std::unordered_map<std::string, ClauseSet*> clauseSetPtrsMap; // maintain a map of clause set pointers keyed by synonym
	std::unordered_map<ClauseSet*, bool> doesClauseSetExistMap; // maintain a map for all the clause sets created so far
	// Look at each clause and 
	// divide them into the right clause sets in which all clauses are dependent on each other for that set,
	// and one set for all clauses with no synonyms at all. (this set is keyed with the empty string "")
	for (unsigned int i = 0; i < clauses.size(); i++) {
		ClauseSet *clauseSet = mapClause(clauses.at(i), &clauseSetPtrsMap);
	}
	for (auto it = clauseSetPtrsMap.begin(); it != clauseSetPtrsMap.end(); it++) {
		ClauseSet *clauseSet = it->second;
		if ( !Utilities::isKeyInMap_TypeType(doesClauseSetExistMap, clauseSet)) {
				doesClauseSetExistMap[clauseSet] = true;
		}	
	}
	for (auto it = doesClauseSetExistMap.begin(); it != doesClauseSetExistMap.end(); it++) {
		independentClauseSets.push_back(*it->first);
	}
	return independentClauseSets;
}

/// Finds all clauses in the given set that have no synonyms, removes them from the given clauses, and returns that set.
Optimizer::ClauseSet Optimizer::extractSynonymlessClauses(ClauseSet *clauses) {
	ClauseSet synonymlessClauses;
	std::vector<int> indexesToRemove;
	for (unsigned int i = 0; i < clauses->size(); i++) {
		const Clause& clause = clauses->at(i);
		if (isSynonymlessClause(clause)) {
			synonymlessClauses.push_back(clause);
			indexesToRemove.push_back(i);
		}
	}
	// Remove the synonymless clauses from the given clause set
	for (int i = (int)indexesToRemove.size() - 1; i >= 0; i--) {
		clauses->erase(clauses->begin() + indexesToRemove.at(i));
	}
	return synonymlessClauses;
}

/// Returns true if there is at least 1 clause remaining.
bool Optimizer::isAnyClauseLeft() {
	return !mClauses.empty();
}

/// Returns the clause with the least complexity.
Clause Optimizer::getLeastComplexityClause() {
	if (mClauses.empty()) {
		// No clauses, return an empty clause.
		return Clause();
	}

	// Here, we are ensured at least one clause. 
	// Find the least complexity clause.
	mLeastComplexityClause = findLeastComplexityClause();

	if (isValidMClauseIndex(mLeastComplexityClause)) {
		// Index in bounds, return it!
		return mClauses[mLeastComplexityClause];
	} else {
		// We should never be here!
		// Print error message and return empty clause.
		cout << "Error in Optimizer::getLeastComplexityClause(): least complexity clause index is out of bounds!\n";
		return Clause();
	}
}

/// Removes the clause of least complexity.
void Optimizer::removeLeastComplexityClause() {

	mLeastComplexityClause = findLeastComplexityClause();

	if (isValidMClauseIndex(mLeastComplexityClause)) {
		mClauses.erase(mClauses.begin() + mLeastComplexityClause);
	} else {
		// Should never be here! 
		// Print out error message.
		cout << "Error in Optimizer::removeLeastComplexityClause(): least complexity clause index is out of bounds!\n";
	}
}

/// Updates the complexity values of all the clauses by using information from the given ResultGraphTable.
void Optimizer::updateComplexityValues(ResultGraphTable& resultGraphTable) {
	for (unsigned int i = 0; i < mClauses.size(); i++) {
		Clause& clause = mClauses[i];
		// Choose the appropriate type of clause and compute the complexity value for it
		double complexityValue;
		switch (clause.type) {
		case Clause::TYPE_RELATIONSHIP_CLAUSE:
			complexityValue = computeComplexityValue(*clause.relationshipEntry, resultGraphTable);
			break;
		case Clause::TYPE_PATTERN_CLAUSE:
			complexityValue = computeComplexityValue(*clause.patternEntry, resultGraphTable);
			break;
		default: // WITH_CLAUSE
			complexityValue = computeComplexityValue(*clause.constraintEntry, resultGraphTable);
			break;
		}
		// Update the clause's complexity value
		clause.complexity = complexityValue;
		//cout << Utilities::clauseToString(mClauses[i]) << " complexity = " << mClauses[i].complexity << endl;
		// Keep track of the least complexity clause
		if ( !isValidMClauseIndex(mLeastComplexityClause)) {
			// The least complexity clause has not been found
			mLeastComplexityClause = i;
		} else {
			// The least complexity clause has been found, 
			// so check its complexity with this complexity to see which is lower.
			if (complexityValue < mClauses[mLeastComplexityClause].complexity) {
				mLeastComplexityClause = i;
			}
		}
	}
}

void Optimizer::updateComplexityValues(SynonymResultsTablePtrMap &tablePtrMap) {
	for (unsigned int i = 0; i < mClauses.size(); i++) {
		Clause& clause = mClauses[i];
		// Choose the appropriate type of clause and compute the complexity value for it
		double complexityValue;
		switch (clause.type) {
		case Clause::TYPE_RELATIONSHIP_CLAUSE:
			complexityValue = computeComplexityValue(*clause.relationshipEntry, tablePtrMap);
			break;
		case Clause::TYPE_PATTERN_CLAUSE:
			complexityValue = computeComplexityValue(*clause.patternEntry, tablePtrMap);
			break;
		default: // WITH_CLAUSE
			complexityValue = computeComplexityValue(*clause.constraintEntry, tablePtrMap);
			break;
		}
		// Update the clause's complexity value
		clause.complexity = complexityValue;
		//cout << Utilities::clauseToString(mClauses[i]) << " complexity value = " << mClauses[i].complexity << endl;
		// Keep track of the least complexity clause
		if ( !isValidMClauseIndex(mLeastComplexityClause)) {
			// The least complexity clause has not been found
			mLeastComplexityClause = i;
		} else {
			// The least complexity clause has been found, 
			// so check its complexity with this complexity to see which is lower.
			if (complexityValue < mClauses[mLeastComplexityClause].complexity) {
				mLeastComplexityClause = i;
			}
		}
	}
}

bool Optimizer::isValidMClauseIndex(int index) {
	return (index >= 0 && index < (int)mClauses.size());
}

int Optimizer::findLeastComplexityClause() {
	if (mClauses.empty()) {
		// No clauses, return -1.
		return -1;
	}

	if (isValidMClauseIndex(mLeastComplexityClause)) {
		// Already know the least complexity clause, so just return it.
		return mLeastComplexityClause;
	}

	// Here, we are ensured to have at least one clause, and that we don't know the least complexity clause.
	// Find it!
	int leastComplexityClause = 0;
	for (unsigned int i = 1; i < mClauses.size(); i++) {
		if (mClauses[i].complexity < mClauses[leastComplexityClause].complexity) {
			leastComplexityClause = i;
		}
	}
	return leastComplexityClause;
}

double Optimizer::computeComplexityValue(const RelationshipEntry &relationshipEntry, ResultGraphTable &rgt) {
	RelationshipType relType = relationshipEntry.relationshipType;
	const std::string& arg1 = relationshipEntry.relationshipArguments[0];
	RelationshipArgumentType argType1 = relationshipEntry.relationshipArgumentTypes[0];
	DesignEntityType synType1 = SpaEnumTranslator::translateRelationshipArgTypeToDesignEntityType(argType1);
	const std::string& arg2 = relationshipEntry.relationshipArguments[1];
	RelationshipArgumentType argType2 = relationshipEntry.relationshipArgumentTypes[1];
	DesignEntityType synType2 = SpaEnumTranslator::translateRelationshipArgTypeToDesignEntityType(argType2);
	
	double complexity = 1.0;
	// 3 Criteria for complexity calculation:
	// 1. Number of tuples between arg1 and arg2
	// 2. Time complexity of the relationship
	// 3. Possible intermediate results of the relationship

	// 1. Number of tuples between arg1 and arg2
	if ( (mSynTable->getDesignEntityType(arg1) != INVALID_DESIGN_ENTITY && (argType1 != STRING)) 
		&& (mSynTable->getDesignEntityType(arg2) != INVALID_DESIGN_ENTITY && (argType2 != STRING)) ) {
		// Both args are synonyms,
		// number of tuples can be gotten using rgt
		complexity *= rgt.getEstimatedNumberOfTuples(arg1, arg2, synType1, synType2, mPkb);
	} else if ( (mSynTable->getDesignEntityType(arg1) != INVALID_DESIGN_ENTITY && (argType1 != STRING)) 
		&& !(mSynTable->getDesignEntityType(arg2) != INVALID_DESIGN_ENTITY && (argType2 != STRING)) ) {
		// arg1 is, but arg2 is NOT a synonym
		// Tuples complexity is just the number of arg1 indexes
		complexity *= rgt.getEstimatedNumberOfTuples(arg1, arg1, synType1, synType1, mPkb);
	} else if ( !(mSynTable->getDesignEntityType(arg1) != INVALID_DESIGN_ENTITY && (argType1 != STRING)) 
		&& (mSynTable->getDesignEntityType(arg2) != INVALID_DESIGN_ENTITY && (argType2 != STRING)) ) {
		// arg 1 is NOT, but arg2 is a synonym
		// Tuples complexity is just the number of arg2 indexes
		complexity *= rgt.getEstimatedNumberOfTuples(arg2, arg2, synType2, synType2, mPkb);
	} else {
		// Both args NOT synonyms
		// Tuples complexity then is just one
		complexity *= 1;
	}
	//cout << "complexity after tuples = " << complexity << endl;

	// 2. Time complexity of the relationship
	complexity *= relTimeComplexities.at(relType);
	//cout << "complexity after time complexity = " << complexity << endl;

	// 3. Possible intermediate results of the relationship
	complexity *= relResultComplexities.at(relType);
	//cout << "complexity after result complexity = " << complexity << endl;

	return complexity;
}

double Optimizer::computeComplexityValue(const PatternEntry &patternEntry, ResultGraphTable &rgt) {
	PatternType patType = patternEntry.patternType;
	const std::string &patternSynonym = patternEntry.synonym;
	DesignEntityType patternSynType = mSynTable->getDesignEntityType(patternSynonym);
	const std::string &arg1 = patternEntry.args[0];
	RelationshipArgumentType argType1 = patternEntry.argSynonymTypes[0];
	DesignEntityType synType1 = SpaEnumTranslator::translateRelationshipArgTypeToDesignEntityType(argType1);
	const std::string &arg2 = patternEntry.args[1];
	RelationshipArgumentType argType2 = patternEntry.argSynonymTypes[1];
	DesignEntityType synType2 = SpaEnumTranslator::translateRelationshipArgTypeToDesignEntityType(argType2);
	const std::string &arg3 = patternEntry.args[2];
	RelationshipArgumentType argType3 = patternEntry.argSynonymTypes[2];
	DesignEntityType synType3 = SpaEnumTranslator::translateRelationshipArgTypeToDesignEntityType(argType3);

	double complexity = 1.0;
	// 3 Criteria for complexity calculation:
	// 1. Number of tuples between arg1 and arg2
	// 2. Time complexity of the relationship
	// 3. Possible intermediate results of the relationship

	// 1. Number of tuples between synonym and one of the arguments (take the maximum number)
	int maxTuples = rgt.getEstimatedNumberOfTuples(patternSynonym, patternSynonym, patternSynType, patternSynType, mPkb);
	if (Utilities::isSynonymTypeRelationshipArgument(argType1)) {
		// arg1 is a synonym, find its tuples with patternSynonym!
		int numTuples = rgt.getEstimatedNumberOfTuples(patternSynonym, arg1, patternSynType, synType1, mPkb);
		if (numTuples > maxTuples) {
			maxTuples = numTuples;
		}
	}
	if (Utilities::isSynonymTypeRelationshipArgument(argType2)) {
		// arg2 is a synonym, find its tuples with patternSynonym!
		int numTuples = rgt.getEstimatedNumberOfTuples(patternSynonym, arg2, patternSynType, synType2, mPkb);
		if (numTuples > maxTuples) {
			maxTuples = numTuples;
		}
	}
	if (Utilities::isSynonymTypeRelationshipArgument(argType3)) {
		// arg3 is a synonym, find its tuples with patternSynonym!
		int numTuples = rgt.getEstimatedNumberOfTuples(patternSynonym, arg3, patternSynType, synType3, mPkb);
		if (numTuples > maxTuples) {
			maxTuples = numTuples;
		}
	}
	complexity *= maxTuples;
	//cout << "complexity after tuples = " << complexity << endl;

	// 2. Time complexity of the relationship
	complexity *= patTimeComplexities.at(patType);
	//cout << "complexity after time complexity = " << complexity << endl;

	// 3. Possible intermediate results of the relationship
	complexity *= patResultComplexities.at(patType);
	//cout << "complexity after result complexity = " << complexity << endl;

	return complexity;
} 

double Optimizer::computeComplexityValue(const ConstraintEntry &constraintEntry, ResultGraphTable &rgt) {
	ConstraintType conType = constraintEntry.constraintType;
	const std::string &arg1 = constraintEntry.constraintArguments[0];
	RelationshipArgumentType argType1 = constraintEntry.constraintArgumentTypes[0];
	DesignEntityType synType1 = SpaEnumTranslator::translateRelationshipArgTypeToDesignEntityType(argType1);
	const std::string &arg2 = constraintEntry.constraintArguments[1];
	RelationshipArgumentType argType2 = constraintEntry.constraintArgumentTypes[1];
	DesignEntityType synType2 = SpaEnumTranslator::translateRelationshipArgTypeToDesignEntityType(argType2);

	double complexity = 1.0;
	// 3 Criteria for complexity calculation:
	// 1. Number of tuples between arg1 and arg2
	// 2. Time complexity of the relationship
	// 3. Possible intermediate results of the relationship

	// 1. Number of tuples between arg1 and arg2
	if (Utilities::isSynonymTypeRelationshipArgument(argType1) && Utilities::isSynonymTypeRelationshipArgument(argType2)) {
		// Both args are synonyms,
		// number of tuples can be gotten using rgt
		complexity *= rgt.getEstimatedNumberOfTuples(arg1, arg2, synType1, synType2, mPkb);
	} else if (Utilities::isSynonymTypeRelationshipArgument(argType1) && !Utilities::isSynonymTypeRelationshipArgument(argType2)) {
		// arg1 is, but arg2 is NOT a synonym
		// Tuples complexity is just the number of arg1 indexes
		complexity *= rgt.getEstimatedNumberOfTuples(arg1, arg1, synType1, synType1, mPkb);
	} else if ( !Utilities::isSynonymTypeRelationshipArgument(argType1) && Utilities::isSynonymTypeRelationshipArgument(argType2)) {
		// arg 1 is NOT, but arg2 is a synonym
		// Tuples complexity is just the number of arg2 indexes
		complexity *= rgt.getEstimatedNumberOfTuples(arg2, arg2, synType2, synType2, mPkb);
	} else {
		// Both args NOT synonyms
		// Tuples complexity then is just one
		complexity *= 1;
	}
	//cout << "complexity after tuples = " << complexity << endl;

	// 2. Time complexity of the relationship
	complexity *= conTimeComplexities.at(conType);
	//cout << "complexity after time complexity = " << complexity << endl;

	// 3. Possible intermediate results of the relationship
	complexity *= conResultComplexities.at(conType);
	//cout << "complexity after result complexity = " << complexity << endl;

	return complexity;
} 

// Computes the complexity value for the given relationship entry using table
double Optimizer::computeComplexityValue(const RelationshipEntry& relationshipEntry, SynonymResultsTablePtrMap &tablePtrMap) {
	RelationshipType relType = relationshipEntry.relationshipType;
	const std::string& arg1 = relationshipEntry.relationshipArguments[0];
	RelationshipArgumentType argType1 = relationshipEntry.relationshipArgumentTypes[0];
	const std::string& arg2 = relationshipEntry.relationshipArguments[1];
	RelationshipArgumentType argType2 = relationshipEntry.relationshipArgumentTypes[1];
	
	double complexity = 1.0;
	// 3 Criteria for complexity calculation:
	// 1. Number of tuples between arg1 and arg2
	// 2. Time complexity of the relationship
	// 3. Possible intermediate results of the relationship

	// 1. Number of tuples between arg1 and arg2
	if (Utilities::isSynonymTypeRelationshipArgument(argType1) && Utilities::isSynonymTypeRelationshipArgument(argType2)) {
		// Both args are synonyms,
		// number of tuples can be gotten using rgt
		complexity *= getEstimatedNumTuplesFromTable(arg1, arg2, tablePtrMap);
	} else if (Utilities::isSynonymTypeRelationshipArgument(argType1) && !Utilities::isSynonymTypeRelationshipArgument(argType2)) {
		// arg1 is, but arg2 is NOT a synonym
		// Tuples complexity is just the number of arg1 indexes
		complexity *= getEstimatedNumTuplesFromTable(arg1, arg1, tablePtrMap);
	} else if ( !Utilities::isSynonymTypeRelationshipArgument(argType1) && Utilities::isSynonymTypeRelationshipArgument(argType2)) {
		// arg 1 is NOT, but arg2 is a synonym
		// Tuples complexity is just the number of arg2 indexes
		complexity *= getEstimatedNumTuplesFromTable(arg2, arg2, tablePtrMap);
	} else {
		// Both args NOT synonyms
		// Tuples complexity then is just one
		complexity *= 1;
	}
	//cout << "complexity after tuples = " << complexity << endl;

	// 2. Time complexity of the relationship
	complexity *= relTimeComplexities.at(relType);
	//cout << "complexity after time complexity = " << complexity << endl;

	// 3. Possible intermediate results of the relationship
	complexity *= relResultComplexities.at(relType);
	//cout << "complexity after result complexity = " << complexity << endl;

	return complexity;
}

// Computes the complexity value for the given pattern entry using table
double Optimizer::computeComplexityValue(const PatternEntry& patternEntry, SynonymResultsTablePtrMap &tablePtrMap) {
	PatternType patType = patternEntry.patternType;
	const std::string &patternSynonym = patternEntry.synonym;
	const std::string &arg1 = patternEntry.args[0];
	RelationshipArgumentType argType1 = patternEntry.argSynonymTypes[0];
	const std::string &arg2 = patternEntry.args[1];
	RelationshipArgumentType argType2 = patternEntry.argSynonymTypes[1];
	const std::string &arg3 = patternEntry.args[2];
	RelationshipArgumentType argType3 = patternEntry.argSynonymTypes[2];

	double complexity = 1.0;
	// 3 Criteria for complexity calculation:
	// 1. Number of tuples between arg1 and arg2
	// 2. Time complexity of the relationship
	// 3. Possible intermediate results of the relationship

	// 1. Number of tuples between synonym and one of the arguments (take the maximum number)
	int maxTuples = getEstimatedNumTuplesFromTable(patternSynonym, patternSynonym, tablePtrMap);
	if (Utilities::isSynonymTypeRelationshipArgument(argType1)) {
		// arg1 is a synonym, find its tuples with patternSynonym!
		int numTuples = getEstimatedNumTuplesFromTable(patternSynonym, arg1, tablePtrMap);
		if (numTuples > maxTuples) {
			maxTuples = numTuples;
		}
	}
	if (Utilities::isSynonymTypeRelationshipArgument(argType2)) {
		// arg2 is a synonym, find its tuples with patternSynonym!
		int numTuples = getEstimatedNumTuplesFromTable(patternSynonym, arg2, tablePtrMap);
		if (numTuples > maxTuples) {
			maxTuples = numTuples;
		}
	}
	if (Utilities::isSynonymTypeRelationshipArgument(argType3)) {
		// arg3 is a synonym, find its tuples with patternSynonym!
		int numTuples = getEstimatedNumTuplesFromTable(patternSynonym, arg3, tablePtrMap);
		if (numTuples > maxTuples) {
			maxTuples = numTuples;
		}
	}
	complexity *= maxTuples;
	//cout << "complexity after tuples = " << complexity << endl;

	// 2. Time complexity of the relationship
	complexity *= patTimeComplexities.at(patType);
	//cout << "complexity after time complexity = " << complexity << endl;

	// 3. Possible intermediate results of the relationship
	complexity *= patResultComplexities.at(patType);
	//cout << "complexity after result complexity = " << complexity << endl;

	return complexity;
}

// Computes the complexity value for the given constraint entry using table
double Optimizer::computeComplexityValue(const ConstraintEntry& constraintEntry, SynonymResultsTablePtrMap &tablePtrMap) {
	ConstraintType conType = constraintEntry.constraintType;
	const std::string &arg1 = constraintEntry.constraintArguments[0];
	RelationshipArgumentType argType1 = constraintEntry.constraintArgumentTypes[0];
	const std::string &arg2 = constraintEntry.constraintArguments[1];
	RelationshipArgumentType argType2 = constraintEntry.constraintArgumentTypes[1];

	double complexity = 1.0;
	// 3 Criteria for complexity calculation:
	// 1. Number of tuples between arg1 and arg2
	// 2. Time complexity of the relationship
	// 3. Possible intermediate results of the relationship

	// 1. Number of tuples between arg1 and arg2
	if (Utilities::isSynonymTypeRelationshipArgument(argType1) && Utilities::isSynonymTypeRelationshipArgument(argType2)) {
		// Both args are synonyms,
		// number of tuples can be gotten using rgt
		complexity *= getEstimatedNumTuplesFromTable(arg1, arg2, tablePtrMap);
	} else if (Utilities::isSynonymTypeRelationshipArgument(argType1) && !Utilities::isSynonymTypeRelationshipArgument(argType2)) {
		// arg1 is, but arg2 is NOT a synonym
		// Tuples complexity is just the number of arg1 indexes
		complexity *= getEstimatedNumTuplesFromTable(arg1, arg1, tablePtrMap);
	} else if ( !Utilities::isSynonymTypeRelationshipArgument(argType1) && Utilities::isSynonymTypeRelationshipArgument(argType2)) {
		// arg 1 is NOT, but arg2 is a synonym
		// Tuples complexity is just the number of arg2 indexes
		complexity *= getEstimatedNumTuplesFromTable(arg2, arg2, tablePtrMap);
	} else {
		// Both args NOT synonyms
		// Tuples complexity then is just one
		complexity *= 1;
	}
	//cout << "complexity after tuples = " << complexity << endl;

	// 2. Time complexity of the relationship
	complexity *= conTimeComplexities.at(conType);
	//cout << "complexity after time complexity = " << complexity << endl;

	// 3. Possible intermediate results of the relationship
	complexity *= conResultComplexities.at(conType);
	//cout << "complexity after result complexity = " << complexity << endl;

	return complexity;
}

bool Optimizer::isSynonymlessClause(const Clause& clause) {
	bool isSynonymless = true;
	RelationshipArgumentType relArg1;
	RelationshipArgumentType relArg2;
	switch (clause.type) {
	case Clause::TYPE_RELATIONSHIP_CLAUSE:
		relArg1 = clause.relationshipEntry->relationshipArgumentTypes[0];
		relArg2 = clause.relationshipEntry->relationshipArgumentTypes[1];
		if (Utilities::isSynonymTypeRelationshipArgument(relArg1)
			|| Utilities::isSynonymTypeRelationshipArgument(relArg2)) {
				isSynonymless = false;
		}
		break;
	case Clause::TYPE_PATTERN_CLAUSE:
		isSynonymless = false; // currently, all pattern entries must have at least one synonym
		break;
	default: // WITH_CLAUSE
		relArg1 = clause.constraintEntry->constraintArgumentTypes[0];
		relArg2 = clause.constraintEntry->constraintArgumentTypes[1];
		if (Utilities::isSynonymTypeRelationshipArgument(relArg1)
			|| Utilities::isSynonymTypeRelationshipArgument(relArg2)) {
				isSynonymless = false;
		}
		break;
	}
	return isSynonymless;
}

Optimizer::ClauseSet* Optimizer::mapClause(const Clause &clause, std::unordered_map<std::string, ClauseSet*> *clauseSetPtrsMap) {
	std::vector<std::string> synonyms; // To store all the synonyms in the given clause
	switch (clause.type) {
	case Clause::TYPE_RELATIONSHIP_CLAUSE:
		extractSynonymsOfRelationshipEntry(&synonyms, *clause.relationshipEntry);
		break;
	case Clause::TYPE_PATTERN_CLAUSE:
		extractSynonymsOfPatternEntry(&synonyms, *clause.patternEntry);
		break;
	default: // WITH_CLAUSE
		extractSynonymsOfConstraintEntry(&synonyms, *clause.constraintEntry);
		break;
	}
	// If no synonyms, map to the empty "" synonym,
	// otherwise we map to the appropriate synonyms
	ClauseSet *clauseSet = NULL;
	std::string emptyString("");
	if (synonyms.empty()) {
		// No synonyms, map to the empty "" synonym
		if (Utilities::isKeyInMap_TypeType(*clauseSetPtrsMap, emptyString)) {
			// Found an already-mapped clause set ptr, so we use that and add this clause in
			clauseSet = (*clauseSetPtrsMap)[emptyString];
			clauseSet->push_back(clause);
		} else {
			// No already-mapped clause set ptr, so we create one and map it
			clauseSet = new ClauseSet();
			clauseSet->push_back(clause);
			(*clauseSetPtrsMap)[emptyString] = clauseSet;
		}
	} else {
		// Have synonyms. 
		// Synonyms might:
		// 1. have no mapped clause ptrs at all, or
		// 2. have only one common mapped clause ptr, or
		// 3. have multipled mapped clause ptrs, different ones for different synonyms.
		// Algorithm:
		// Find the set of unique mapped clause ptrs, and join all these clause sets into one, add this clause,
		// then map all synonyms to that one unioned clause set.
		// If no mapped clause ptrs at all, then just create a clause set containing just this clause
		// and map all synonyms to that clause set.
		std::unordered_map<ClauseSet*, bool> uniqueClauseSetPtrsMap;
		getAllUniqueClauseSetPtrs(synonyms, &uniqueClauseSetPtrsMap, *clauseSetPtrsMap);
		if (uniqueClauseSetPtrsMap.empty()) {
			// No mapped clause ptrs at all.
			// Just create a clause set containing just this clause and map all synonyms to that clause set
			clauseSet = new ClauseSet();
			clauseSet->push_back(clause);
			// Map
			for (unsigned int i = 0; i < synonyms.size(); i++) {
				(*clauseSetPtrsMap)[synonyms.at(i)] = clauseSet;
			}
		} else {
			// Have mapped clause ptrs. Merge all of them into one clausePtr then map all synonyms to it.
			auto it = uniqueClauseSetPtrsMap.begin();
			clauseSet = it->first;
			// Merge
			for (it++; it != uniqueClauseSetPtrsMap.end(); it++) {
				const ClauseSet *otherClauseSet = it->first;
				for (unsigned int i = 0; i < otherClauseSet->size(); i++) {
					clauseSet->push_back(otherClauseSet->at(i));
				}
			}
			// Map
			for (unsigned int i = 0; i < synonyms.size(); i++) {
				(*clauseSetPtrsMap)[synonyms.at(i)] = clauseSet;
			}
		}
	}
	return clauseSet;
}

void Optimizer::getAllUniqueClauseSetPtrs(const std::vector<std::string> &synonyms, 
		std::unordered_map<ClauseSet*, bool> *uniqueClauseSetPtrsMap, 
		const std::unordered_map<std::string, ClauseSet*> &clauseSetPtrsMap) {
	
			for (unsigned int i = 0; i < synonyms.size(); i++) {
				const std::string& synonym = synonyms[i];
				if (Utilities::isKeyInMap_TypeType(clauseSetPtrsMap, synonym)) {
					ClauseSet *clauseSet = clauseSetPtrsMap.at(synonym);
					if ( !Utilities::isKeyInMap_TypeType(*uniqueClauseSetPtrsMap, clauseSet)) {
						uniqueClauseSetPtrsMap->insert( std::make_pair(clauseSet, true) );
					}
				}
			}
}

// Finds all the synonyms in relEntry (if any) and puts them into the given synonyms set
void Optimizer::extractSynonymsOfRelationshipEntry(std::vector<std::string> *synonyms, const RelationshipEntry &relEntry) {
	RelationshipArgumentType relArg1 = relEntry.relationshipArgumentTypes[0];
	RelationshipArgumentType relArg2 = relEntry.relationshipArgumentTypes[1];
	if (Utilities::isSynonymTypeRelationshipArgument(relArg1)) {
		synonyms->push_back(relEntry.relationshipArguments[0]);
	}
	if (Utilities::isSynonymTypeRelationshipArgument(relArg2)) {
		synonyms->push_back(relEntry.relationshipArguments[1]);
	}
}

// Finds all the synonyms in patternEntry (if any) and puts them into the given synonyms set
void Optimizer::extractSynonymsOfPatternEntry(std::vector<std::string> *synonyms, const PatternEntry &patternEntry) {
	synonyms->push_back(patternEntry.synonym);

	RelationshipArgumentType patternArg1 = patternEntry.argSynonymTypes[0];
	RelationshipArgumentType patternArg2 = patternEntry.argSynonymTypes[1];
	RelationshipArgumentType patternArg3 = patternEntry.argSynonymTypes[2];
	if (Utilities::isSynonymTypeRelationshipArgument(patternArg1)) {
		synonyms->push_back(patternEntry.args[0]);
	}
	if (Utilities::isSynonymTypeRelationshipArgument(patternArg2)) {
		synonyms->push_back(patternEntry.args[1]);
	}
	if (Utilities::isSynonymTypeRelationshipArgument(patternArg3)) {
		synonyms->push_back(patternEntry.args[2]);
	}
}

// Finds all the synonyms in constraintEntry (if any) and puts them into the given synonyms set
void Optimizer::extractSynonymsOfConstraintEntry(std::vector<std::string> *synonyms, const ConstraintEntry &constraintEntry) {
	RelationshipArgumentType conArg1 = constraintEntry.constraintArgumentTypes[0];
	RelationshipArgumentType conArg2 = constraintEntry.constraintArgumentTypes[1];
	if (Utilities::isSynonymTypeRelationshipArgument(conArg1)) {
		synonyms->push_back(constraintEntry.constraintArguments[0]);
	}
	if (Utilities::isSynonymTypeRelationshipArgument(conArg2)) {
		synonyms->push_back(constraintEntry.constraintArguments[1]);
	}
}

int Optimizer::getEstimatedNumTuplesFromTable(const std::string &synonym1, const std::string &synonym2, const SynonymResultsTablePtrMap &tablePtrMap) {
	//cout << "synonym1 = " << synonym1 << " & synonym2 = " << synonym2 << endl;
	if (synonym1 == synonym2) {
		// just return the number of indexes for synonym1
		if (Utilities::isKeyInMap_TypeType(tablePtrMap, synonym1)) {
			// Has a table, so return the unique indexes
			return tablePtrMap.at(synonym1)->getColumnItemCountMap(synonym1).size();
		} else {
			// Does not have a table, so getAllIndexes for the synonym type
			return getNumIndexes(mSynTable->getDesignEntityType(synonym1));
		}
	}

	// Here, synonym1 is NOT the same as synonym2
	int numTuples = 0;
	if (Utilities::isKeyInMap_TypeType(tablePtrMap, synonym1) && Utilities::isKeyInMap_TypeType(tablePtrMap, synonym2)) {
		// Both synonyms have a table
		SynonymResultsTable *table1 = tablePtrMap.at(synonym1);
		SynonymResultsTable *table2 = tablePtrMap.at(synonym2);
		if (table1 == table2) {
			// same table
			numTuples = table1->getNumRows();
		} else {
			// different table
			numTuples = table1->getColumnItemCountMap(synonym1).size() * table2->getColumnItemCountMap(synonym2).size();
		}
	} else if ( !Utilities::isKeyInMap_TypeType(tablePtrMap, synonym1) && !Utilities::isKeyInMap_TypeType(tablePtrMap, synonym2)) {
		// Both synonyms do NOT have a table
		numTuples = getNumIndexes(mSynTable->getDesignEntityType(synonym1)) 
			* getNumIndexes(mSynTable->getDesignEntityType(synonym2));
	} else if ( !Utilities::isKeyInMap_TypeType(tablePtrMap, synonym1)) {
		// synonym1 does NOT have a table, while synonym2 does
		SynonymResultsTable *table2 = tablePtrMap.at(synonym2);
		numTuples = getNumIndexes(mSynTable->getDesignEntityType(synonym1)) 
			* table2->getColumnItemCountMap(synonym2).size();
	} else {
		// synonym1 has a table, while synonym2 does NOT
		SynonymResultsTable *table1 = tablePtrMap.at(synonym1);
		numTuples =  table1->getColumnItemCountMap(synonym1).size() 
			* getNumIndexes(mSynTable->getDesignEntityType(synonym2));
	}
	return numTuples;
}

int Optimizer::getNumIndexes(DesignEntityType synType) {
	int numIndexes = 0;
	switch (synType) {
	case ASSIGN:
		numIndexes = mPkb->getLinesByEntity(Type::Entity::ASSIGNMENT_LINE_ENTITY).size();
		break;
	case CALL:
		numIndexes = mPkb->getLinesByEntity(Type::Entity::CALL_LINE_ENTITY).size();
		break;
	case CONSTANT:
		numIndexes = mPkb->getConstants().size();
		break;
	case IF:
		numIndexes = mPkb->getLinesByEntity(Type::Entity::IF_LINE_ENTITY).size();
		break;
	case PROCEDURE:
		numIndexes = mPkb->getProcIndices().size();
		break;
	case PROG_LINE:
		// Fallthrough
	case STMT:
		numIndexes = mPkb->getLines().size();
		break;
	case VARIABLE:
		numIndexes = mPkb->getVarIndices().size();
		break;
	case WHILE:
		numIndexes = mPkb->getLinesByEntity(Type::Entity::WHILE_LINE_ENTITY).size();
		break;
	default: // INVALID
		numIndexes = mPkb->getLines().size(); // arbitrarily use the number of lines in the program
		cout << "Optimizer::getNumIndexes() for a DesignEntityType currently not supported\n";
		break;
	}
	return numIndexes;
}